package com.kznnc.data_structure.sort.one;

/**
 * @Description 插入排序
 * 1. 将所有要排序的数字,划分为有序序列, 和无序序列
 * 2. 有序序列可以从一个开始, 将无序的数字, 插入到有序序列中应该存放的位置
 * 3. 将无序序列, 插入到有序序列,插入完毕, (重复2步骤)
 * @Author houchenkai
 * @Created Date: 2021/6/24 19:07
 * @ClassName
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] a = {6, 8, 9, 7, 2, 4, 1, 3, 5};
        int n = a.length;
        // 外层是无序的数字 一个个将无序数字插入到有序序列
        for (int i = 1; i < a.length; i++) {
            // 获取当前要插入的元素
            int data = a[i];
            // j 已经排序好的最后一个元素位置
            int j = i - 1;
            // 从后往前遍历 已经排序好的元素
            for (; j >= 0; j--) {
                // 将当前要插入的元素 与排序好的元素做对比
                // 如果待插入元素小于 已排序元素 则将已排序好的元素后移
                if (a[j] > data) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            // j的坐标是 已排序好的 做对比的元素  对比完后应该插入此下标的后面
            a[j + 1] = data;
        }
        for (int i : a) {
            System.out.println(i);
        }

    }


}
